package leetcode_800;

import java.util.Stack;

/**
 *@author 周杨
 *MonotoneIncreasingDigits_738 给定一个正整数N 找到比其等或者小的最大单调数
 *describe:从后往前遍历 直至找到降序的index 将其减一  后面全赋为9
 *2018年10月15日 下午12:37:41
 */
public class MonotoneIncreasingDigits_738 {
	
	public static void main(String[] args) {
		MonotoneIncreasingDigits_738 test=new MonotoneIncreasingDigits_738();
		System.out.println(test.monotoneIncreasingDigits(243));
		System.out.println(test.monotoneIncreasingDigits(1010));
		System.out.println(test.monotoneIncreasingDigits(323));
	}
	
	public  int monotoneIncreasingDigits(int N) {

	       
        char[] x = String.valueOf(N).toCharArray();

        int mark = x.length;
        for(int i = x.length-1;i>0;i--){
            if(x[i]<x[i-1]){
                mark = i-1;
                x[i-1]--;
            }
        }
        for(int i = mark+1;i<x.length;i++){
            x[i] = '9';
        }
        return Integer.parseInt(new String(x));
    }
	
	/**
	 * describe:贪心思想错误 如120 就直接给99 应该给119
	 * 2018年10月15日 下午12:55:13
	 */
	public int monotoneIncreasingDigits1(int N) {
        if(N<10)
        	return N;
        int temp=N;
        Stack<Integer> stack=new Stack<Integer>();
        while(temp>0) {
        	stack.push(temp%10);
        	temp/=10;
        }
        int []arr=new int[stack.size()];
        int index=0;
        while(index<arr.length) {
        	arr[index++]=stack.pop();
        }
        for(int i=1;i<arr.length;++i) {
        	if(arr[i]<arr[i-1]) {//发现逆序
        		for(int j=1;j<arr.length;++j) {
        			if(arr[j]<arr[0]) {//那么不能用第一位构建 第一位降级
        				temp=9;
    					index=1;
    					while(index<arr.length-1) {//-1表示降级
    						temp=temp*10+9;
    						++index;
    					}
        				if(arr[0]==1) {//第一位是1 如101 降为99	
        					return temp;
        				}
        				else {
        					temp+=(arr[0]-1)*Math.pow(10,arr.length-1);
        					return temp;
        				}
        			}
        		}
        		//否则就用全是第一位构建
        		temp=arr[0];
        		index=1;
        		while(index<arr.length) {
        			temp=temp*10+arr[0];
        			++index;
        		}
        		return temp;
        	}
        }
        return N;//N合法
    }
}
